The digital representation of surfaces has been an intense area of research for both the computer graphics and applied mathematics communities for the past decade. The idea of using functions to represent shapes is desirable since it allows the development of highly efficient algorithms for modeling and rendering such shapes. Storage of values needed for image rendering has also been a concern given that heretofore it has been necessary to store large amounts of data as part of the process of representing such shapes. Such storage requirements lead to the usage of large amounts of memory.
For example, Boolean operations in constructive solid modeling can be applied to the functions representing the surfaces as opposed to the surfaces themselves, making it straightforward to generate unions, intersections, and subtractions from MRI data, morphing, collision detection, and interface tracking such as in a fluid simulation.
Recall that a function is a mathematical rule for corresponding one set of numerical values to another set. When plotted, or otherwise rendered visually, a function can describe a particular shape. For example, the function y=x2 has the shape of a parabola when plotted on x- and y-axes. A function is a general term which applies to the whole entity which makes values in one set to correspond to other values in another set. The formula, or equation, which goes with a function (e.g., y=x2) is itself called the rule. Functions also are used to map points in space to numerical values, such as is done by an implicit surface function. A signed distance function, denoted by Φ, is a special case of an implicit surface function. Signed distance functions are used to relate a given point in space to the point's distance from the closest point on the interface (not an arbitrary value as may be the case of a generic implicit function representation). Points inside the shape are taken to have negative distance values from the interface, points on the interface have zero distance from the interface, and points outside the shape are taken to have positive distance values from the interface.
If we create a 3D grid around an object, for each point on the grid, we can compute such point's distance to the object's interface. Thus, the 3D grid can be used to approximate the object's shape; grid cells with some corners that evaluate inside and others outside will certainly contain points on the interface. Techniques such as trilinear interpolation are used to compute such points up to an error tolerance. The above described 3D grid representation can be viewed as an explicit representation of a signed distance function. In other words, memory must be allocated for the entire 3D grid, and signed distance values stored for each grid point.
The need to allocate memory for the signed distance functions for each grid point tends to impose constraints on the maximum grid resolution. For instance, a 3D grid resolution of 100 cells along each axis would require 100×100×100×8 bytes=8 MB RAM, (i.e., 8 MB=8 million bytes of Random Access Memory (RAM)), assuming double precision, which is the standard precision used in computing for these types of values. If we increase the resolution to 1000 cells along each axis, we will need 8 GB of memory, which is hardly practical even using the most powerful computer systems nowadays. Note that the higher the resolution, the better the approximation, resulting in a tradeoff between memory usage and the accuracy required by the application at hand.
Therefore, there is a need for an improved system and method for representing signed distance functions in a computer graphics environment.